package com.hle;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.PriorityQueue;

class Solution {

	class Node {
		public int i;
		public int j;

		public Node(int a, int b) {
			i = a;
			j = b;
		}
	}

	public List<List<Integer>> kSmallestPairs(int[] A, int[] B, int k) {
		if (A == null || B == null || A.length == 0 || B.length == 0 || k <= 0) {
			return new ArrayList<>();
		}
		final int N = A.length;
		final int M = B.length;

		// 小根堆
		PriorityQueue<Node> Q = new PriorityQueue<>((v1, v2) -> A[v1.i] + B[v1.j] - A[v2.i] - B[v2.j]);

		for (int i = 0; i < N; i++) {
			Q.add(new Node(i, 0));
		}

		List<List<Integer>> ans = new ArrayList<>();
		for (int i = 0; i < k && !Q.isEmpty(); i++) {
			Node p = Q.poll();
			ans.add(Arrays.asList(A[p.i], B[p.j]));
			if (p.j + 1 < M) {
				Q.add(new Node(p.i, p.j + 1));
			}
		}
		return ans;
	}
}
